package BinaryTree;

public class TreeOperations2 {

    public static int gerKthLevel(TreeNode root,int k) {
        //求第k层的结点个数
        if(root==null) {
            return 0;
        }

        if (k==1) {
            return 1;
        }

        int leftSize=gerKthLevel(root.left,k-1);
        int rightSize=gerKthLevel(root.right,k-1);

        return leftSize+rightSize;
    }

    public static int getHeight(TreeNode root) {
        //二叉树的高度
        if(root==null) {
            return 0;
        }

        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);

        return Integer.max(leftHeight,rightHeight)+1;
    }

    public static boolean contains(TreeNode root,int e) {
        //用先序遍历判断元素e是否存在
        if(root==null) {
            return false;
        }
        if(root.val==e) {
            return true;
        }
        //先去左子树找，有则返回true
        if(contains(root.left,e )) {
            return true;
        }
        //再去右子树找，无则返回false
        return contains(root.right,e);
    }

    public static TreeNode nodeOf(TreeNode root,int e) {
        //用先序遍历查找元素e,找到返回元素e的引用，没找到返回null
        if(root==null) {
            return null;
        }
        if(root.val==e) {
            return root;
        }

        //先去左子树找，找到则返回的是 != null
        TreeNode r=nodeOf(root.left,e);
        if(r!=null) {
            return r;
        }
        //再去左子树找，找到则返回相应引用
        return nodeOf(root.right,e);

    }

    public static boolean containsNode(TreeNode root,TreeNode node) {
        //用先序遍历判断结点node是否存在
        if(root==null) {
            return false;
        }

        if(root==node) {
            return true;
        }

        //左子树中查找
        if(containsNode(root.left,node)) {
            return true;
        }

        return containsNode(root.right,node);

    }


    public static void main(String[] args) {
        TreeNode root=BuildTree构建树.buildTree2();

        TreeNode node=nodeOf(root,'f');
        System.out.println(node);

        System.out.println(gerKthLevel(root, 4));
        System.out.println(getHeight(root));
    }
}
